package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/16 15:22
 * @description: 力扣97 交错字符串
 * 思路：
 * 定义dp(i,j):表示s1的前i个元素和s2的前j个元素是否能组成交替的s3的i+j个元素
 * 如果s1的第i个元素和s3的第i+j个元素相等，那么dp[i][j]否为为true，则取决于||| 暂不分析
 */
public class Interleave {
    public static void main(String[] args) {

    }
}
class Interleave_Soulution{

    public boolean isInterleave(String s1,String s2,String s3){
        int n = s1.length();
        int m = s2.length();
        int len = s3.length();
        if(m+n != len){
            return false;
        }
       boolean [][]dp = new boolean[n+1][m+1];
       dp[0][0] = true;
       for(int i = 0; i <=len;i++){
           for(int j = 0;j <= len;j++){
               int p = i+j-1;
               if(i > 0){
                   dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(p);
               }
               if(j > 0){
                   dp[i][j] = dp[i][j] || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(p));
               }
           }
       }
       return dp[n][m];
    }
}